package main.动态规划;

/**
 * @author tmh
 * @date 2024/9/7 22:30
 * @description
 */
public class T62不同路径 {
    //dp[i][j]是到达(i,j)最多的路径
    //对于边界上的位置，都只有一条路径可以到达，所以初始值都为1
    //对于非边界上的路径，到达该位置的路径为到达到达上面一个位置的路径加上
    //到达左面位置的路径之和dp[i][j]=dp[i-1][j]+dp[i][j-1]
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        //为第一行赋值初始值
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        //为第一列赋值初始值
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        //为其他元素赋值初始值
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}
